package leetcode.tree;

/**
 * 给出一个完全二叉树，求出该树的节点个数。
 *
 * 说明：
 *
 * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *
 * 示例:
 *
 * 输入:
 *     1
 *    / \
 *   2   3
 *  / \  /
 * 4  5 6
 *
 * 输出: 6
 *
 * 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class CountDoubleTree {
    private static int i = 0;

    public int countNodes1(TreeNode root) {
        i = 0;
        if (root != null){
            getNum(root);
        }
        return i;
    }

    /**
     * 翻转一棵二叉树。
     *
     * 示例：
     *
     * 输入：
     *
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     * 输出：
     *
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
     *
     */
    public TreeNode invertTree(TreeNode root) {
        if (root != null){
            TreeNode tmp = root.right;
            root.right = root.left;
            root.left = tmp;
            invertTree(root.left);
            invertTree(root.right);
        }
        return root;
    }

    /**
     * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
     *
     * 说明：
     * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
     *
     * 示例 1:
     *
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 1
     * 示例 2:
     *
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 3
     */
    public int kthSmallest(TreeNode root, int k) {
        int i = countNodes(root.left);
        if (i == k-1){
            return root.val;
        }

        if (i < k-1){
            return kthSmallest(root.right, k-i-1);
        }else {
            return kthSmallest(root.left, k);
        }

    }


    public int countNodes(TreeNode root) {
        return root != null ? 1 + countNodes(root.right) + countNodes(root.left) : 0;
    }

    public static void getNum(TreeNode node){
        i++;
        if (node.right != null){
            getNum(node.right);
        }
        if (node.left != null){
            getNum(node.left);
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static void main(String[] args){

    }
}
